package com.awei.study.dataStructure.tree;

import org.junit.jupiter.api.Test;
import sun.reflect.generics.tree.Tree;

import javax.print.attribute.IntegerSyntax;
import javax.xml.soap.Node;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @Author liweilong
 * @Date 2023/6/15 16:06
 * 二叉树练习
 * 1.判断是否为对称二叉树
 * 2.获取树最大深度
 */

public class BinaryTree {

    /**
     * 1.判断是否为对称二叉树
     */
    @Test
    public void test_isSymmetric() {
        TreeNode root = new TreeNode(
                new TreeNode(new TreeNode(null,4,null),2,null),
                1,
                new TreeNode(null,3,null)
        );
        System.out.println(isSymmetric(root));
        root = new TreeNode(
                new TreeNode(new TreeNode(null,3,null),2,new TreeNode(null,4,null)),
                1,
                new TreeNode(new TreeNode(null,4,null),2,new TreeNode(null,3,null))
        );
        System.out.println(isSymmetric(root));
    }

    /**
     *
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {
        if(root.left == null || root.right == null)
            return false;
        return check(root.left,root.right);
    }

    /**
     *
     * @param left
     * @param right
     * @return
     *      1
     *     / \
     *    2   3
     *   /
     *  4
     */
    public boolean check(TreeNode left,TreeNode right) {
        if (left == null && right == null)
            return true;
        if (left == null || right == null) {
            return false;
        }
        if (left.value != right.value) return false;

        return check(left.left, right.right) && check(left.right, right.left);
    }

    /**
     * 2.获取树最大深度
     */
    @Test
    public void test_treeDepth() {
        /**
         *          1
         *         / \
         *        2   3
         *       /
         *      4
         */
        TreeNode root = new TreeNode(
                new TreeNode(new TreeNode(null,4,null),2,null),
                1,
                new TreeNode(null,3,null)
        );
        System.out.println("treeDepth_dfs = " + treeDepth_dfs(root));
        System.out.println("treeDepth_traversal = " + treeDepth_traversal(root));
        System.out.println("treeDepth_bfs = " + treeDepth_bfs(root));
        /**
         *          1
         */
        root = new TreeNode(null,1,null);
        System.out.println(treeDepth_dfs(root));
        System.out.println(treeDepth_bfs(root));
        /**
         *          1
         *         /
         *        2
         */
        root = new TreeNode(new TreeNode(null,2,null),1,null);
        System.out.println(treeDepth_dfs(root));
        System.out.println(treeDepth_bfs(root));
    }


    /**
     * 2.1获取树最大深度——递归
     * @param tree
     * @return
     */
    public int treeDepth_dfs(TreeNode tree) {
        if(tree == null)    return 0;
        int leftChildDepth = treeDepth_dfs(tree.left);
        int rightChildDepth = treeDepth_dfs(tree.right);
        return Integer.max(leftChildDepth,rightChildDepth) + 1;
    }

    /**
     * 2.2获取树最大深度——遍历
     * @param tree
     * @return
     */
    public int treeDepth_traversal(TreeNode tree) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode root = tree;
        int max = 0;
        TreeNode pop = null;
        while(root != null || !stack.isEmpty()) {
            if(root != null) {
                stack.push(root);
                if(max < stack.size()) max = stack.size();
                root = root.left;
//                System.out.println(root.value);
            }else {
                TreeNode top = stack.peek();
                if(top.right == null || top.right == pop) {
                    pop = stack.pop();
                }else {
                    root = top.right;
                }
//                System.out.println(root.value);
            }
        }
        return max;
    }
    /**
     * 2.2获取树最大深度——广度优先搜索
     * @param tree
     * @return
     */
//    @SuppressWarnings("all")
    public int treeDepth_bfs(TreeNode tree) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(tree);
        int depth = 0;
        while(!queue.isEmpty()) {
            int size = queue.size();
            depth++;
            for (int i = 0; i < size; i++) {
                TreeNode pop = queue.poll();
                assert pop != null;
                if(pop.left != null)
                    queue.offer(pop.left);
                if(pop.right != null)
                    queue.offer(pop.right);
            }
        }
        return depth;
    }
}
